#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = p.size();
        int m = s.size();
        s = " " + s;
        p = " " + p;
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++)
        {
            //dp[0][i] = true;
            //dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (j > 0 && (p[i] == '?' || p[i] == s[j]))
                {

                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[i] == '*')
                {
                    //if(i==1)
                    //{
                        //dp[i][j] = true;
                    //}
                    for (int k = 0; k <= j; k++)
                    {
                        if (dp[i - 1][k] == true)
                        {
                            dp[i][j] = true;
                            break;
                        }

                    }
                    //cout<<i<<":"<<j<<" "<<dp[i][j]<<endl;
                }
                else
                {
                    dp[i][j] = false;//dp[i-1][j]?true:dp[i][j-1];
                }
                //cout<<dp[i][j]<<"  ";
            }
            //cout<<endl;

        }
        return dp[n][m];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = p.size();
        int m = s.size();
        s = " " + s;
        p = " " + p;
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        //for(int i = 1;i<=n;i++)
        //{
            //dp[0][i] = true;
            //dp[i][0] = true;
        //}
        int i = 1;
        while (p[i] == '*')
        {
            for (int j = 0; j <= m; j++)
            {
                dp[i][j] = true;
            }
            i++;
        }
        for (; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (j > 0 && (p[i] == '?' || p[i] == s[j]))
                {

                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[i] == '*')
                {
                    //if(i==1)
                    //{
                        //dp[i][j] = true;
                    //}
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    //for(int k = 0;k<=j;k++)
                    //{
                        //if(dp[i-1][k]==true)
                        //{
                            //dp[i][j] = true;
                            //break;
                        //}

                    //}
                    //cout<<i<<":"<<j<<" "<<dp[i][j]<<endl;
                }
                else
                {
                    dp[i][j] = false;//dp[i-1][j]?true:dp[i][j-1];
                }
                //cout<<dp[i][j]<<"  ";
            }
            //cout<<endl;

        }
        return dp[n][m];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = p.size();
        int m = s.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        s = " " + s;
        p = " " + p;
        int index = 2;
        dp[0][0] = true;
        while (index <= n && p[index] == '*')
        {
            //cout<<index<<endl;
            dp[index][0] = true;
            index += 2;
        }

        int i = 1;
        //while(p[i]=='*')
        //{
            //for(int j = 0;j<=m;j++)
            //{
                //dp[i][j] = true;
            //}
            //i++;
        //}

        for (; i <= n; i++)
        {
            cout << i << endl;
            for (int j = 1; j <= m; j++)
            {
                if (p[i] == '*')
                {
                    //if(p[i-1]=='.')
                    //{
                        //dp[i][j] = dp[i-2][j]||dp[i][j-1];

                    //}
                    //else //if(p[i-1]==s[j])
                        //dp[i][j] = dp[i-2][j]||dp[i][j-1];
                    dp[i][j] = dp[i - 2][j] || (p[i - 1] == '.' || p[i - 1] == s[j]) && dp[i][j - 1];

                }
                else if (p[i] == '.' || p[i] == s[j])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;

        }
        return dp[n][m];
    }
};

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size();
        int m = s2.size();
        int k = s3.size();
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        if (n + m != k)
            return false;
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= m; i++)
        {
            if (s2[i] == s3[i])
                dp[0][i] = true;
            else
                break;
        }
        for (int i = 1; i <= n; i++)
        {
            if (s1[i] == s3[i])
                dp[i][0] = true;
            else
                break;
        }
        for (int i = 1; i <= n; i++)
        {
            cout << i << endl;
            for (int j = 1; j <= m; j++)
            {
                int tmp = i + j;
                if (s1[i] == s3[tmp] && dp[i - 1][j])
                {
                    dp[i][j] = true;
                    continue;
                }
                if (s2[j] == s3[tmp] && dp[i][j - 1])
                {
                    dp[i][j] = true;
                    continue;
                }
            }
            cout << endl;
        }
        return dp[n][m];
    }
};

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        s1 = " " + s1;
        s2 = " " + s2;

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int ret = 0;
        for (int i = 1; i <= n; i++)
        {
            ret += s1[i];
            //dp[0][i] = dp[0][i-1]+s2[i];
        }
        for (int i = 1; i <= m; i++)
        {
            ret += s2[i];
            //dp[i][0] = dp[i-1][0]+s1[i];
        }
        cout << ret << endl;
        for (int i = 1; i <= n; i++)
        {
            cout << i << endl;
            for (int j = 1; j <= m; j++)
            {
                if (s1[i] == s2[j])
                {
                    dp[i][j] = dp[i - 1][j - 1] + s1[i];
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;

        }
        return ret - 2 * dp[n][m];
    }
};

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //sort(nums1.begin(),nums1.end());
        //sort(nums2.begin(),nums2.end());
        int n = nums1.size();
        int m = nums2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int ret = 0;
        for (int i = 1; i <= n; i++)
        {
            //cout<<i<<endl;
            for (int j = 1; j <= m; j++)
            {
                if (nums1[i - 1] == nums2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                ret = max(ret, dp[i][j]);
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;
        }
        return ret;
    }
};